% Copyright 2004 by Till Tantau <tantau@users.sourceforge.net>.
%
% In principle, this file can be redistributed and/or modified under
% the terms of the GNU Public License, version 2.
%
% However, this file is supposed to be a template to be modified
% for your own needs. For this reason, if you use this file as a
% template and not specifically distribute it as part of a another
% package/program, I grant the extra permission to freely copy and
% modify this file as you see fit and even to delete this copyright
% notice. 

\documentclass[11pt]{beamer}
\setbeamertemplate{caption}[numbered]
% Replace the \documentclass declaration above
% with the following two lines to typeset your 
% lecture notes as a handout:
%\documentclass{article}
%\usepackage{beamerarticle}
\usepackage[utf8]{inputenc}
\usepackage[noend]{algpseudocode}
\usepackage[T1]{fontenc}
%\usepackage{algorithmic}
\usepackage{algorithmicx}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage[french,british]{babel}
\usepackage{algorithm}
\usepackage{caption}
\usepackage{subcaption}


\usepackage[font=scriptsize,skip=3pt]{caption}
%\setlength{\textfloatsep}{1.0pt plus 1.0pt minus 2.0pt}

\setbeamertemplate{footline}[frame number]

% There are many different themes available for Beamer. A comprehensive
% list with examples is given here:
% http://deic.uab.es/~iblanes/beamer_gallery/index_by_theme.html
% You can uncomment the themes below if you would like to use a different
% one:
%\usetheme{AnnArbor}
%\usetheme{Antibes}
%\usetheme{Bergen}
%\usetheme{Berkeley}
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{boxes}
%\usetheme{CambridgeUS}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
%\usetheme{default}
%\usetheme{Frankfurt}
%\usetheme{Goettingen}
%\usetheme{Hannover}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
%\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
\usetheme{Montpellier}
%\usetheme{PaloAlto}
%\usetheme{Pittsburgh}
%\usetheme{Rochester}
%\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}

%=====================================================Slide 1
\titlegraphic{
\begin{figure}[!htb]
\minipage{0.07\textwidth}
  \includegraphics[width=\linewidth]{images/ctu-logo}
\endminipage\hfill
\minipage{0.07\textwidth}
  \includegraphics[width=\linewidth]{images/ifi-logo}
\endminipage\hfill
\minipage{0.07\textwidth}
  \includegraphics[width=\linewidth]{images/auf-logo}
\endminipage\hfill
\minipage{0.07\textwidth}
  \includegraphics[width=\linewidth]{images/unh-logo}
\endminipage\hfill
\end{figure}
}

\title{Algorithme parallèle de Descente de gradient stochastique multi-classes pour la classification d'images
}

\author[1]{Réalisateur : NGUYEN Quoc Khai, promotion 17, IFI \\[\baselineskip]
Superviseurs : DO Thanh Nghi(CTU), PHAM Nguyen Khang(CTU) et HO Tuong Vinh(IFI)
}

\date{Stage M2 réalisé à la laboratoire IDPL, CTU, Cantho, 2014}


% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{sgd pour la classification d'images}
% This is only inserted into the PDF information catalog. Can be left
% out. 

% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

% \pgfdeclareimage[height=0.5cm]{university-logo}{university-logo-filename}
% \logo{\pgfuseimage{university-logo}}

% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
\AtBeginSection[]
{
  \begin{frame}<beamer>{Plan de présentation}
    \tableofcontents[currentsection, currentsubsection]
  \end{frame}
}

% Let's get started
\begin{document}
\begin{otherlanguage}{french}
\begin{frame}
  \titlepage
\end{frame}


%=====================================================Slide 2
\begin{frame}{Plan de présentation}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}


\section{Introduction}
\subsection{Motivation}
%=====================================================Slide 6
\begin{frame}{Classification d'images}
\begin{figure}[ht!]
\centering
\includegraphics[width=105mm]{images/classification}
\caption{La classification d'image}
\vspace{-2.0em}
\label{fig:classification}
\end{figure}
\end{frame}

%=====================================================Slide 4
\begin{frame}{Application de la classification d'images}
La classification d'images est appliquée dans plusieurs domaines importants :
\begin{itemize}
\pause
\item Reconnaissance des chiffres sur des chèques
\pause
\item Reconnaissance des codes postaux pour la classification automatique des courriers
\pause
\item Reconnaissance des visages pour l'authentification
\end{itemize}
\end{frame}

%=====================================================Slide 6
\begin{frame}{Difficulté de la classification d'images}
Les données sorties des images sont complexes :
\begin{itemize}
\pause
\item Les dimension sont grandes
\pause
\item Beaucoup de classes
\end{itemize}
\pause
Solution\\
$\rightarrow$ Il faut améliorer la vitesse
\end{frame}

\subsection{Contribution}
%=====================================================Slide 6
\begin{frame}{Contribution}
Pendant ce stage, nous avons proposé :
\begin{itemize}
\pause
\item Un algorithme SGD-SVM multi-classes
\pause
\item Une version parallèle de cet algorithme
\pause
\item Implémentation de MC-SGD-Toy pour étudier l'algorithme MC-SGD
\end{itemize}
\pause
Résultats expérimentaux :
\begin{itemize}
\item Égale au SVM pour la classification multi-classes
\item Plus vite que le SVM de 26 fois à 3902 fois
\end{itemize}
\end{frame}


\section{État de l'art}
\subsection{Processus de la classification d'images}
%=====================================================Slide 6
\begin{frame}{Processus de la classification d'images}
\begin{enumerate}
\pause
\item Extraction des caractéristiques des images : obtenir des vecteurs de caractéristiques (SIFT)
\pause
\item Construire un dictionnaire et calculer le fréquence de chaque mot apparaît dans chaque image : obtenir des histogrammes de chaque image (BOW)
\pause
\item Application SVM pour l'apprentissage automatique sur des histogrammes
\end{enumerate}
\end{frame}


%=====================================================Slide 6
\begin{frame}{Processus de la classification d'images (2)}
\begin{figure}[ht!]
\centering
\includegraphics[width=105mm]{images/svm-processus}
\caption{Processus de la classification d'image}
\vspace{-2.0em}
\label{fig:processussvm}
\end{figure}
\end{frame}

\subsection{Apprentissage automatique}
\subsubsection*{SVM}
%=====================================================Slide 14
\begin{frame}{Méthode SVM}
\begin{itemize}
\item Méthode d'apprentissage supervisé importante
\item Cherche l'hyperplan optimal séparant les données en deux classes
\end{itemize}

\begin{figure}[ht!]
\centering
\includegraphics[width=60mm]{images/svm1}
\caption{Classification linéaire}
\label{fig:svm1}
\end{figure}
\end{frame}

%=====================================================Slide 15
\begin{frame}{Méthode SVM - support hyperplan}
\begin{figure}[ht!]
\centering
\includegraphics[width=60mm]{images/svm2}
\caption{Support hyperplan}
\label{fig:svm2}
\end{figure}
\end{frame}

%=====================================================Slide 15
\begin{frame}{Méthode SVM - hyperplan optimal}
\begin{figure}[ht!]
\centering
\includegraphics[width=60mm]{images/svm3}
\caption{L'hyperplan optimal}
\label{fig:svm3}
\end{figure}
\end{frame}

%=====================================================Slide 15
\begin{frame}{Méthode SVM - problème}
\begin{figure}[ht!]
\centering
\includegraphics[width=60mm]{images/svm4}
\caption{Erreurs de SVM}
\label{fig:svm4}
\end{figure}
\begin{itemize}
\item SVM obtient $w$ et $b$ après avoir trouvé la solution du programme quadratique $f(w, b, z)$ (détaille dans le rapport)
\end{itemize}\end{frame}


\subsubsection*{SGD}
%=====================================================Slide 6
%\begin{frame}{Introduction - méthode SGD}
%\begin{itemize}
%\item SVM est satisfait pour la classification d'image, mais cette méthode est lent
%$\rightarrow$ SGD est une bonne choix pour améliorer la vitesse
%\item Même processus avec SVM pour la classification d'image. SGD remplace SVM dans l'étape 3
%\item Nous développons, parallélisons un algorithme de classification SGD multi-classes pour classification d'image de grand taille
%\end{itemize}
%\end{frame}


%=====================================================Slide 19
\begin{frame}{Méthode SGD-SVM}
\begin{itemize}
\item Ignorer $b$ dans le programme quadratique $f(w, b, z)$ pour obtenir le programme $\Psi(w, [x, y])$(détaille dans le rapport)
%\item Ne pas résoudre le problème de programme de quadratique
\pause
\item $w$ est mis à jour en T étapes
\pause
\item A chaque étape $t$, SGD prend aléatoirement n exemples $(x_i, y_i)$ pour calculer le sous-gradient et met à jour $w_{t+1}$
\pause
\begin{equation}
w_{t+1} = w_t - \eta_t\nabla_w{\Psi(w_t, [x_i, y_i])}
\label{f9}
\end{equation}
\end{itemize}
\pause
\begin{algorithm}[H]
\caption{\scriptsize L'algorithm d'apprentissage SGD-SVM binaire}
\label{sgdal}
\scriptsize
\begin{algorithmic}[1]
\Procedure{trainBinaireSGDSVM}{$X$, $y$, $\lambda$, $T$, $n$}

\State Initialiser $w_1 = 0$

\For{\texttt{t = 0; t < T; t++}}

\State $\eta_t = \frac{1}{\lambda t}$

\State \texttt{Choisir n exemples aléatoire dans X}
\State $w_{t+1} = w_t - \eta_t\nabla_w{\Psi(w_t, [x_i, y_i])}$
\EndFor
\State Return $w_{t}$
\EndProcedure
\end{algorithmic}
\end{algorithm}
\end{frame}

\section{Algorithme SGD-SVM multi-classes}
\subsection{Algorithme linéaire de SGD-SVM multi-classes}
%=====================================================Slide 20
\begin{frame}{Méthode SGD - propriété}
\begin{itemize}
\item SGD résout le problème de classification de 2 classes\\
\pause
$\rightarrow$ Comment résoudre le problème de multi-classes ?
\pause
\item Diviser d'abord le problème en plusieurs problèmes de 2 classes
\pause
\item Chaque problème de 2 classes est traité par la classification binaire
\item One-versus-one \cite{vv95} et one-versus-all \cite{uk99}.
\end{itemize}
\end{frame}


%=====================================================Slide 22
\begin{frame}{Méthode MC-SGD - 1-vs-1}
\begin{figure}[ht!]
\centering
\includegraphics[width=110mm]{images/1vs1}
\caption{One-versus-one}
\label{fig:1vs1}
\end{figure}
\begin{itemize}
\item Construire \textit{k(k-1)/2} (k est le nombre de classes) classificateurs
\pause
\item Prédiction : voter et la majorité des classificateurs va être choisie
\end{itemize}
\end{frame}


%=====================================================Slide 23
\begin{frame}{Méthode MC-SGD - 1-vs-all}
\begin{itemize}
\item Problèmes de 1-vs-1 : beaucoup de classificateurs (k(k-1)/2)
\item 1-vs-all construit \textit{k} classificateurs
\end{itemize}

\begin{figure}[ht!]
\centering
\includegraphics[width=110mm]{images/1vsall}
\caption{One-versus-all}
\label{fig:1vs1}
\end{figure}
\pause
Prédiction : la classe ayant la distance la plus courte entre son classificateur et l'exemple d'entrée est choisie.
\end{frame}


\subsection{Équilibration de MC-SGD}
%=====================================================Slide 29
\begin{frame}{MC-SGD - problème de balance}
\begin{itemize}
\item Si le problème de 1000 classes, on a 1 exemple positive et 999 exemples négatives
\item Les exemples positives sont rarement choisis (\emph{0.1\%})
\item Les exemples négatives sont très souvent choisis (\emph{99.9\%})
\pause
\item Comment balancer l'ensemble d'exemples ?
\end{itemize}
\pause
Solutions
\begin{itemize}
\item Sous-échantillonnage : augmentation la probabilité sélectionnée de l'exemple positive
\pause
\item Coût de données : mettre à jours $w$ par des différents cas par rapport des erreurs obtenues
\end{itemize}
\end{frame}


\subsection{Parallélisation de MC-SGD}
%=====================================================Slide 31
\begin{frame}{Parallélisation de MC-SGD}
\begin{itemize}
\item MC-SGD est linaire, apprendre des modèles l'un après l'autre
\item Sur des ordinateurs multi-cœurs : pas économiser des ressources\\
\pause
$\rightarrow$ Parallélisation MC-SGD est une bonne solution
\pause
\item k processeurs apprennent k modèles en parallèle
\pause
\item Nous choisissons OpenMP pour paralléliser cet algorithme
\end{itemize}
\end{frame}


%=====================================================Slide 31
\begin{frame}{SGD-Toy de MC-SGD}
Interface pour la démonstration de MC-SGD, se base sur SVM-Toy\cite{cl01}\\
Données :
\begin{itemize}
\item Chaque point est un exemple
\item x, y sont 2 caractéristiques d'exemples
\end{itemize}
On applique MC-SGD pour la classification

\begin{figure}[ht!]
\centering
\includegraphics[width=50mm]{images/toy}
\caption{MC-SGD-Toy}
\label{fig:toy}
\end{figure}
\end{frame}


%=====================================================Slide 31
%\begin{frame}
%\begin{figure}[ht!]
%\centering
%\includegraphics[width=85mm]{images/sgd-paral}
%\caption{Descente de gradient stochastique parallèle}
%\label{al:sgd-paral}
%\end{figure}
%\end{frame}

\section{Expérimentation}
\begin{frame}{Expérimentation}
Logiciels références
\begin{itemize}
\item Extraction des caractéristiques : SIFT[low99], K-Means(pour clustering)
\item Classification binaire : SGD (implémentation Pegasos).
\end{itemize}
Matériels utilisées
\begin{itemize}
\item PC core-i7, 4 double cœurs, 3G RAM
\item Système d'exploitation : GNU-Linux Fedora 20
\end{itemize}
\pause
Nos implémentations
\begin{itemize}
\pause
\item Classification multi-classes: MC-SGD et MC-SGD parallèle, implémentés en C/C++ en utilisant l'OpenMP
\pause
\item Outils pour étudier notre algorithme: MC-SGD-Toy, basé sur SVM-Toy\cite{cl01}
\end{itemize}
\end{frame}

\subsection{Jeux de données}
%=====================================================Slide 34
\begin{frame}{Jeux de données}
\begin{table}
\begin{center}
    \begin{tabular}{ | c | c | c | c | c |}
    \hline
    Données & \#classes & \#train & \#test & \#mots(bow) \\ \hline

    Cal 101 & 101 & 1515 & 1515 & 124000 \\ \hline

    Cal 7 3D & 7 & 4290 & 2145 & 5000 \\ \hline 

    ImgNet 3d & 10 & 4450 & 2225 & 5000 \\ \hline

    ImgNet & 10 & 4450 & 2225 & 50000 \\ \hline
    
    Protein & 3 & 14895 & 6621 & 357 \\ \hline
    
    Mnist & 10 & 30000 & 30000 & 780 \\ \hline

    \end{tabular}
\end{center}
\caption{Information sur des données}
\label{tab:infod1}
\end{table}
\end{frame}


\subsection{Résultat obtenu}
%=====================================================Slide 38
\begin{frame}{Classification d'images avec SVM et SGD multi-classes}
%\begin{itemize}
%\item SVM : function linaire
%\item SGD : -iter 1000 -k 10 -lambda 0.6
%\end{itemize}

\begin{table}
\begin{center}
    \begin{tabular}{ | c | c | c | c | c | c |}
    \hline
    Données & SVM(\%) & SGD(\%) & SVM(s) & SGD(s) & $\frac{SVM(s)}{SGD(s)}$ \\ \hline

    Cal 101 & 61.52 & 65.12 & 2873 & 106.95 & \textbf{26.9} \\ \hline
    
    Cal 7 3D & 91.52 & 88.3 & 113.4 & 0.81 & \textbf{140} \\ \hline 

    ImgNet 3d & 76.54 & 75.8 & 144 & 0.90 & \textbf{160} \\ \hline
    
    ImgNet & 84.08 & 86.58 & 327 & 1.64 & \textbf{199.4} \\ \hline

    Protein & 68.23 & 68.41 & 551 & 0.20 & \textbf{2755} \\ \hline
    
    Mnist & 86.92 & 86.46 & 2810 & 0.72 & \textbf{3902.8} \\ \hline
    
    \end{tabular}
\end{center}
\caption{Comparaison entre LIBSVM et MC-SGD parallèle}
\label{tab:pmcsvm}
\end{table}
\end{frame}


%=====================================================Slide 31
\begin{frame}{Classification avec SVM et MC-SGD}
\begin{figure}[ht!]
\centering
\includegraphics[width=110mm]{images/res1}
\caption{Comparaison de SVM et MC-SGD (SVM/MC-SGD)}
\label{fig:res}
\end{figure}
\end{frame}

\section{Conclusion}
%=====================================================Slide 40
\begin{frame}{Conclusion}
\begin{itemize}
\item Nous avons étudié le processus pour la classification d'images utilisant la méthode SVM
\pause
\item Nous avons implémenté la méthode MC-SGD de classification multi-classes
\pause
\item Résoudre le problème de balance quand la base de données est de multi-classes
\pause
\item Paralléliser MC-SGD
\pause
\item Implémenter MC-SGD-Toy pour étudier l'algorithme MC-SGD
\pause
\item MC-SGD est plus vite que SVM, correspond bien pour la classification d'image
\end{itemize}
\end{frame}

%=====================================================Slide 42
\begin{frame}{Perspective}
\begin{itemize}
\item SGD est difficile de choisir des paramètres entrées
\pause
\item Nous étudierons pour chercher des paramètres optimales de la méthode
\pause
\item Nous testerons aussi des bases d'images plus grandes tel que ImageNet
\pause
\item Nous développerons pour que SGD s'adapte à la classification de vidéos
\end{itemize}
\end{frame}


\end{otherlanguage}

% All of the following is optional and typically not needed. 
\section*{Références}
%=====================================================Slide 43
\begin{small}

\begin{frame}{Références}
\begin{thebibliography}{9}

\bibitem{sss07} S.Shwartz, Y.Singer and N.Srebro \emph{ Pegasos: Primal esti-
mated sub-gradient solver for svm.}, Proceedings of the Twenty-Fourth International Conference Machine Learning, pp. 807-814. ACM (2007)

\bibitem{low99} David G. Lowe, \emph{Object Recognition from Local Scale-Invariant Features,} In proceeding of the 7th International conference of computer vision, pages 1150 - 1157, Corfou, Grèce, 1999.
 
\bibitem{vv95} V.Vapnik, \emph{The Nature of Statistical Learning Theory.}, Springer, New York (1995).

\bibitem{uk99} U.Krebel, \emph{Pairwise classification and support vector machines}, Support Vector Learning, Advances in Kernel Methods. pp.255–268. (1999).

\bibitem{cl01} C.Chang and C.Lin, \emph{LIBSVM – a library for support vector machines}, http://www.csie.ntu.edu.tw/~cjlin/libsvm (2001).


\end{thebibliography}
\end{frame}

\end{small}

%=====================================================Slide 44
\begin{frame}
 \Huge Merci pour votre attention!!!!!
\end{frame}

\end{document}
